package com.code.array;


import java.util.*;
import java.util.stream.Collectors;

public class arrayTest {


    /**
     * 1.两数之和
     * @param nums
     * @param target
     * @return
     */
    public static int[] twoSum(int[] nums, int target){

       for(int i=0;i<nums.length;i++){
           for(int j=i+1;j<nums.length;j++){
               if(nums[i]+nums[j]==target){
                   return new int[]{i,j};
               }
           }
       }
        return new int[]{0,0};
    }


    /**
     * 49.字母异位词分组
     * @param strs
     * @return
     */
    public static List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key=chars.toString();
            map.computeIfAbsent(key,k->new ArrayList<>()).add(str);
        }
        return new ArrayList<>(map.values());
    }

    /**
     * 128. 最长连续序列
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {

        if(nums.length==0){
            return 0;
        }

        Arrays.sort(nums);
        int minNum = nums[0];
        int total=1;
        int result=1;

        for(int i=1;i<nums.length;i++){

            if(minNum==nums[i]){
                continue;
            }

            if(minNum+1==nums[i]){
                total++;
            }else{
                total=1;
            }

            if(result<total){
                result=total;
            }

            minNum=nums[i];
        }
        return result;
    }

    /**
     * 283. 移动零
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[j++]=nums[i];
            }
        }

        for(int i=0;i<nums.length-j;i++){
            nums[j+i]=0;
        }

    }

    /**
     *11.盛水最多的容器
     * 采用双指针思想，每次移动最短的边
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int maxResult=0;
        int min=0;
        int max=height.length-1;
        int area=0;
        while(min<max){
            if(height[min]<=height[max]){
                area=height[min]*(max-min);
                min++;
            }else{
                area=height[max]*(max-min);
                max--;
            }
            if(area>maxResult){
                maxResult=area;
            }
        }
        return maxResult;
    }

    /**
     * 15。三数之和
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<Integer> sum=null;
        List<List<Integer>> list=new ArrayList<>();
        if(nums == null || nums.length < 3) return list;
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0){
                break;
            }
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left=i+1;
            int right=nums.length-1;
            while(left<right){
                int s=nums[i]+nums[left]+nums[right];
                if(s==0){
                    sum=new ArrayList<>();
                    sum.add(nums[i]);
                    sum.add(nums[left]);
                    sum.add(nums[right]);
                    list.add(sum);
                    while(left<right && nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right && nums[right]==nums[right-1]){
                        right--;
                    }

                    left++;
                    right--;
                }
                else if(s<0){
                    left++;
                }else if(s>0){
                    right--;
                }
            }
        }
        return list;
    }

    /**
     * 接雨水
     *双指针， 每次移动值小的一边， 当前指针盛的雨水数量= min(leftMax,rightMax)-height[x]   左边最大的值和右边最大值 取最小-当前柱子高度
     * 在移动过程中，判断当前指针是否大于左边或右边最大值，若大于则进行更新
     * @param height
     * @return
     */
    public static int trap(int[] height){
        int left=0;
        int right=height.length-1;
        int leftMax=height[left];
        int rightMax=height[right];
        int result=0;
        while(left<right){
            if(leftMax<=rightMax){
                left++;
                leftMax=Math.max(leftMax,height[left]);
                result=result+leftMax-height[left];
            }else{
                right--;
                rightMax=Math.max(rightMax,height[right]);
                result=result+rightMax-height[right];
            }
        }
        return result;
    }


    /**
     * 求无重复最大字串长度，  使用滑动窗口思想，
     * 无重复的直接使用右指针往set里面加，有重复的调用左指针 去除，
     * 在移动过程中，保留最大长度值
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int result = 0;
        char[] chars = s.toCharArray();
        int left = 0;
        int right=0;
        HashSet<Character> set = new HashSet<>();
        while(left < chars.length && right<chars.length){
            if(set.contains(chars[right])){
                //碰见重复的元素，直接移动左指针； 删除完成后 会继续right判断，因为 right没有更新 。
//                while(left<right ){
                    set.remove(chars[left]);
                    left++;
//                }
            }else{
                set.add(chars[right]);
                right++;
                if(set.size()>result){
                    result=set.size();
                }
            }
        }

        return result;
    }

    /**
     * 438. 找到字符串中所有字母异位词
     * 直接排序滑动窗口有超时的风险，   优化为
     * 使用数组， 因为题中给出的所有元素都是小写字母， 所以可以先建立一个 长度为26的一维数组，
     * 每次去比较 每个元素出现的频率，  这里有个情况要注意的是 滑动窗口每次只滑一位，所以要在外面进行一个初始化操作，初始化完成之后直接判断 当前是否符合异位词
     *
     * 一维数组如何分别存储 每个字母出现的频率    使用  String.charAt[i]-'a'   即可
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length()){
            return new ArrayList<>();
        }
        List<Integer> result=new ArrayList<>();
        int [] sArray=new int[26];
        int [] pArray=new int[26];

        int left=0;
        int right=p.length();
        for(int i=0;i<p.length();i++){
            sArray[s.charAt(i)-'a']++;
            pArray[p.charAt(i)-'a']++;
        }
        // 检查初始窗口
        if (Arrays.equals(sArray, pArray)) {
            result.add(0);
        }

        while(left<s.length()-p.length()){
            sArray[s.charAt(left)-'a']--;
            sArray[s.charAt(right)-'a']++;
            left++;
            right++;
            if(Arrays.equals(sArray,pArray)){
                result.add(left);
            }
        }
        return result;

    }

    /**
     * 560.和为 k 的子数组
     *
     * 前缀和[i]-k=x； x在前缀和出现的次数相加既为答案
     * 使用哈希表记录 每个前缀出现的次数，
     * 前缀和 默认第0个元素出现频率是0
     * 视频讲解 https://www.bilibili.com/video/BV1gN411E7Zx/?spm_id_from=333.337.search-card.all.click&vd_source=b5cc04f324fc9d6ee48a5febd77392fc
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k) {
        int total=0;
        int sum=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        for(int i=0;i<nums.length;i++){
            sum=sum+nums[i];
            //满足条件的前缀和， 这里和put不能调换顺序，  计算顺序应和手算保持一致。 put在前就相当于 去看后面一个数了
            if(map.containsKey(sum-k)){
                total=total+map.get(sum-k);
            }
            //设置前缀和出现频率
            map.put(sum,map.getOrDefault(sum,0)+1);

        }
        return total;
    }


//    /**
//     * 239. 滑动窗口最大值
//     *
//     * 暴力破解超时
//     *
//     * @param nums
//     * @param k
//     * @return
//     */
//    public static int[] maxSlidingWindow(int[] nums, int k) {
//        List<Integer> resultList=new ArrayList<>();
//        if(nums.length<=k){
//            int max=Arrays.stream(nums).max().getAsInt();
//            resultList.add(max);
//            return new int[]{max}; // 直接创建int数组返回;
//        }
//        int left=0;
//        int right=k-1;
//
//        while(left<=nums.length-k ){
//            int max=-100000;
//            for(int i=left;i<=right;i++){
//                if(max<nums[i]){
//                    max=nums[i];
//                }
//            }
//            resultList.add(max);
//            left++;
//            right++;
//        }
//
//        int[] resultArray = new int[resultList.size()];
//        for (int i = 0; i < resultList.size(); i++) {
//            resultArray[i] = resultList.get(i); // 自动拆箱
//        }
//        return resultArray;
//    }

    /**
     * 239. 滑动窗口最大值
     *    //右边进  保证当前要添加的值要小于队列中的某个值，如果没有那就放到队首     队列首值最大
     *   //左边出  当队列中第一个值小于滑动窗口最左边的值 就移除   滑动窗口最左边值：left=i-k+1
     *   //记录队首值
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        int [] result=new int[nums.length-k+1];
        Deque<Integer> deque=new ArrayDeque<>();
        //时刻记得队列中存储的是数组的下标 而非数组元素
        for(int i=0;i<nums.length;i++){
            //右边进 1.(条件删除)  当前值如果比队列中最后一个值大，那么久将队列中的最后一个值 删除，
            //直到当前值小于队列中的某个值，或者当前值成为最大值  当队列为空时，表示当前值是最大值
            while(!deque.isEmpty() && nums[i]>=nums[deque.getLast()]){
                deque.removeLast();
            }
            //右边进 2.(添加)
            deque.addLast(i);
            //左边出  当队列中第一个值小于滑动窗口最左边的值 就移除
            int left=i-k+1;  //滑动窗口最左边的值
            if(deque.getFirst()<left){
                deque.removeFirst();
            }
            //记录最大值
            if(left>=0){
                result[left]=nums[deque.getFirst()];
            }

        }
        return result;
    }


    /**
     * 76.最小覆盖字串
     *
     * https://www.bilibili.com/video/BV1ta411a7UK?spm_id_from=333.788.videopod.episodes&vd_source=f8e7ecfd2de9e15f5cd47a12393fc38b&p=31
     *
     *  解题思路 使用滑动窗口 右指针往右移动 当滑动窗口内的值符合 t 的时候(valid==tMap.size()) 左指针开始持续移动并且将窗口之外的字符从map中减一，直到不符合  以此类推
     *
     *  难点 如何判断当前滑动窗口内的值 是否符合 t  ===>>> 以 t 和滑动窗口构建两个哈希表，key为字符，value为出现频率
     *  如何对比两个map的值大小呢？   设计一个变量valid用来存储滑动窗口中符合 t 字符的数量
     * @param s
     * @param t
     * @return
     */

    public static String minWindow(String s, String t) {
        int maxValue = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();

        // 初始化sMap和tMap
        Map<Character, Integer> sMap = new HashMap<>();
        Map<Character, Integer> tMap = new HashMap<>();
        // 填充tMap
        for (int i = 0; i < tArray.length; i++) {
            tMap.put(tArray[i], tMap.getOrDefault(tArray[i], 0) + 1);
        }
        //统计滑动窗口中符合的字符数量
        int valid=0;
        int start=0;
        int len=Integer.MAX_VALUE;

        while (right < sArray.length) {
            char cur=s.charAt(right);
            right++;
            //只添加 在tMap中出现过的字符
            if(tMap.containsKey(cur)){
                //添加
                sMap.put(cur,sMap.getOrDefault(cur,0)+1);
                //取sMap和tMap中对应key的 value  如果值相同说明当前字符 已经对上了，valid+1
                if(Objects.equals(tMap.get(cur),sMap.get(cur))){
                    valid++;
                }
            }
            //进入下面循环说明 已经在滑动窗口中找到所有符合 t 中的字符， 下一步就是往左滑动left
            while(valid==tMap.size()){
                //right-left 表示当前滑动窗口的长度， len始终记录当前最小的滑动窗口长度  start记录最小滑动窗口的起始位置
                if(len>right-left){
                    len=right-left;   //因为 while下面第三行 先right++，所以这里直接减left不用在+1。
                    start=left;
                }
                //判断当前舍弃的 值 是否符合 t 中字符，如果是 t 中字符 那么对应的 vaild-1，并且 sMap中的值也要-1
                char leftNum=s.charAt(left);
                if(tMap.containsKey(leftNum)){
                    if(Objects.equals(tMap.get(leftNum),sMap.get(leftNum))){
                        valid--;
                    }
                    sMap.put(leftNum,sMap.get(leftNum)-1);
                }
                left++;
            }

        }
        //三元表达式   逻辑判断 ?true:false
        return len==Integer.MAX_VALUE?"":s.substring(start,start+len);
    }

    /**
     * 53.最大子数组和
     *
     * //https://www.bilibili.com/video/BV18M4m1m7sM/?spm_id_from=333.1391.0.0&vd_source=f8e7ecfd2de9e15f5cd47a12393fc38b
     *         //局部最优：当前 “连续和”为负数的时候立刻放弃，从下一个元素重新计算，因为负数加上下一个元素“连续和”只会越来越小
     *         //全局最优：读取最大“连续和”
     *         //局部最优的情况下，并记录最大的连续和，推出全局最优
     *
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        //没有思路  只能想到使用前缀和来解决，但是后面不知道如何写   前缀和+贪心算法思想

        //https://www.bilibili.com/video/BV18M4m1m7sM/?spm_id_from=333.1391.0.0&vd_source=f8e7ecfd2de9e15f5cd47a12393fc38b
        //局部最优：当前 “连续和”为负数的时候立刻放弃，从下一个元素重新计算，因为负数加上下一个元素“连续和”只会越来越小
        //全局最优：读取最大“连续和”
        //局部最优的情况下，并记录最大的连续和，推出全局最优
        int sum=0;
        int result=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            sum=sum+nums[i];
            if(sum>result){
                result=sum;
            }
            if(sum<0){
                sum=0;
            }
        }
        return result;
    }


    /**
     * 56. 合并区间
     *    //排序+贪心算法
     *         //排序：按照start值进行升序排列，若start值相同，则按end升序排列
     *         //贪心合并  遍历排序后的区间，维护一个当前合并区间[start,end], 然后遍历数组，若end>=下一个数组的start(有重叠) 则end=max(end,下一个的end) 取最大值，
     *         //                                                                     若end<下一个数组的start(无重叠) 将当前start，end加入结果序列
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b) ->{
            //比较起始值
            if(a[0]==b[0]){
                //起始值相同 比较结束值
                return a[1]-b[1];  //如果返回值为负，会调换他们的位置，如果为正那么不会动
            }else{
                //起始值不同，比较起始值
                return a[0]-b[0];
            }
        });
        List<int[]> result=new ArrayList<>();
        //start end 初始值 取第一个，下面for就从1开始了
        int start=intervals[0][0];
        int end=intervals[0][1];

        for(int i=1;i<intervals.length;i++){
            int [] interval=intervals[i];
            if(end>=interval[0]){
                //有重叠 将end替换为最大值
                //end=interval[1];  //因为题中给出提示 start[i]<end[i] 说明 interval[0]一定小于interval[1]    原始写法为 end=Math.max(end,interval[1]);
                end=Math.max(end,interval[1]);
            }else{
                //没有重叠  放入结果序列，并更新start和end
                result.add(new int[]{start,end});
                start=intervals[i][0];
                end=intervals[i][1];
            }
        }
        //将最后一个合并的区间加入结果列表
        result.add(new int[]{start,end});
        return result.toArray(new int[0][]);
    }

    /**
     *198.转轮数组
     * 非最优解
     * @param nums
     * @param k
     */
    public void rotate1(int[] nums, int k) {
        //难点在 模除 计算 (i+k)%n=i
        int n=nums.length;
        int []temp=new int[n];
        for(int i=0;i<n;i++){
            temp[(i+k)%n]=nums[i];
        }
        System.arraycopy(temp,0,nums,0,n);
    }

    /**
     *198.转轮数组 最优解
     * 使用翻转链表实现
     *                                  示例： 1 2 3 4 5 6 7  k=3
     *                                  翻转： 7 6 5 4 3 2 1
     * 观察得出；前三个翻转  后四翻转组成结果       5 6 7 1 2 3 4
     *
     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int n=nums.length;
        //有k>数组长度的情况， 所以进行一个模除   数组长度为5，翻转8次和3次是一样的   当翻转到第五次的时候 就是原数组
        k=k % n;
        reverse(nums,0,n-1);
        reverse(nums,0,k-1);
        reverse(nums,k,n-1);
    }

    public static void reverse(int[] nums,int n,int j){
        while(n<j){
            int temp=nums[n];
            nums[n]=nums[j];
            nums[j]=temp;
            n++;
            j--;
        }
    }


    public int[] productExceptSelf(int[] nums) {
        //题目中已经给出了提示  前缀积和后缀积
        // answer[i]=nums[i]的前缀积*nums[i]的后缀积
        //所以重点去求前缀和后缀积  最后相乘即可
        //重点 首元素的前缀积默认为1；尾元素的后缀积为1
        int n=nums.length;
        int [] left=new int[n];
        int [] right=new int[n];
        int [] answer=new int[n];
        // 对于索引为 '0' 的元素，因为左侧没有元素，所以 L[0] = 1
        left[0]=1;
        // 对于索引为 'length-1' 的元素，因为右侧没有元素，所以 R[length-1] = 1
        right[n-1]=1;
        for(int i=1;i<n;i++){
            left[i]=left[i-1]*nums[i-1];
        }
        for(int i=n-2;i>=0;i--){
            right[i]=right[i+1]*nums[i+1];
        }
        for(int i=0;i<n;i++){
            answer[i]=left[i]*right[i];
        }
        return answer;
    }

    /**
     *41.缺失的第一个正数
     * @param nums
     * @return
     */
    public static int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int n=nums.length;
        int temp=0;
        for(int i=0;i<n;i++){
            if(nums[i]>0){
                temp++;
                if(temp!=nums[i] && temp<nums[i]){
                    return temp;
                }else if(temp==nums[i]+1){
                    temp--;
                }
            }
        }
        return ++temp;
    }

    /**
     * 73.矩阵置零
     *
     * 重点： 设置整列为0的时候应该遍历行 *****
     *       设置整行为0的时候应该遍历列 *****
     *
     * @param matrix
     */
    public void setZeroes(int[][] matrix) {
        List<int[]> list = new ArrayList<>();
        int rows = matrix.length;     // 总行数
        int cols = matrix[0].length;  // 总列数
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    list.add(new int[]{i, j});
                }
            }
        }
        for (int[] num : list) {
            int row = num[0]; //行索引
            int col = num[1];    //列索引
            // 重点：设置整列 (固定列索引col，遍历所有行)
            for (int i = 0; i < rows; i++) {
                matrix[i][col] = 0;
            }
            // 重点：设置整行 (固定行索引row，遍历所有列)
            for (int j = 0; j < cols; j++) {
                matrix[row][j] = 0;
            }
        }
    }

    /**
     * 54.螺旋矩阵
     *
     *       //整体思想是 按照 右 下 左 上 依次遍历整个数组，遇到边界或者遍历过的数组，将遍历过的数组都置为Integer.MAX_VALUE
     *         //就向右转九十度， 右转90度的实现方式是  对  dir+1模除4；dir为当前坐标中的一维值；因为整体遍历顺序是 右 下 左 上
     *         // 所以坐标 按照这个逻辑去设计，dir的默认值也就是0
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        //结果序列
        List<Integer> ans=new ArrayList<>();
        //右 下 左 上    可以理解为 坐标，每次 遍历移动都要从这个里面获取
        int[][] dirs=new int [][]{{0,1},{1,0},{0,-1},{-1,0}};   //坐标

        //定义边界
        int row=matrix.length;
        int col=matrix[0].length;

        int left=0;
        int right=0;
        int dir=0;
        //依次顺序遍历，总共移动 row*col ===>  行*列 次
        for(int i=0; i<row*col; i++){
            //将当前元素加入结果序列
            ans.add(matrix[left][right]);
            matrix[left][right]=Integer.MAX_VALUE;
            //按照当前移动格式，计算下一次的移动位置 ===>每次计算位置 都要去坐标中获取值进行计算
            int nextLeft=dirs[dir][0]+left;
            int nextRight=dirs[dir][1]+right;
            //如果下一个位置越界或者是已经遍历过的元素，则进行旋转   越界是指四个方向
            if(nextLeft>=row || nextRight>=col || nextLeft<0 || nextRight<0 || matrix[nextLeft][nextRight]==Integer.MAX_VALUE){
                //进行旋转
                dir=(dir+1)%4;
            }
            //使用坐标进行相加
            left=left+dirs[dir][0];
            right=right+dirs[dir][1];
        }
        return ans;
    }

    /**
     *48.旋转图像
     *
     *   思路：：  原始矩阵 到结果矩阵可经过两次变化 得到  (i,j)=>(j,i)=>(每行中元素翻转)
     *
     *
     *         //重点 第一次交换时的内层循环 j=i，如果j=0；那么会交换两次
     *           //    第二次翻转行中元素时，使用双指针进行翻转
     *         // 例如：i=0，j=1时， 交换一次，当i=1，j=0又会交换一次；这样就相当于没有变化
     *
     * @param matrix
     */
    public void rotate(int[][] matrix) {

        for(int i=0;i<matrix.length;i++){
            //第一次变化 (i,j) ==>(j,i)
            //注意内层循环起始值 j=i 否则会置换两次  (i,j)=>(j,i)=>(i,j)
            for(int j=i;j<matrix.length;j++){
                int temp=matrix[i][j];
                matrix[i][j]=matrix[j][i];
                matrix[j][i]=temp;
            }
        }

        //第二次变化   二维数组中每行元素翻转  例如第一行 (0,0) (0,1) (0,2)==>(0,2)  (0,1) (0,0)
        for(int i=0;i<matrix.length;i++){
            int left=0;
            int right=matrix.length-1;
            while(left<right){
                int temp=matrix[i][left];
                matrix[i][left]=matrix[i][right];
                matrix[i][right]=temp;
                left++;
                right--;
            }
        }
    }

    /**
     * 240.搜索二维矩阵
     *
     *    思路：  //使用排除法做，每次都从右上角开始进行计算，
     *         //如果右上角的元素值小于target，那么说明这一行都是小于target的，直接跳过
     *         //如果右上角的元素值大于target，那么说明这一列都是大于target的，直接跳过
     *
     *      重点：每次循环只能判断一次，所以使用if else if格式
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        int i=0;  //当前行
        int j=matrix[0].length-1;  //当前列
        while(i<matrix.length && j>=0){
            //是否相等，相等直接返回true
            if(matrix[i][j]==target){
                return true;
            }else if(matrix[i][j]<target){    //小于target 排除当前行
                i++;
            }else if(matrix[i][j]>target){     //大于target 排除当前列
                j--;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        String a="AAADOBECODEBANC";
        String b="ABC";
        int [] nums=new int []{0,2,2,1,1};
        int [][] matrix =new int[][]{{-1,3}};
//        int k=3;
//        System.out.println(searchMatrix(matrix,3));
    }
}
